package graph;

import java.util.*;

public class MinimumHeightTrees310 {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        LinkedList<Integer> deque =  new LinkedList<>();

        if(edges==null||edges.length==0){
            for (int i = 0; i < n; i++) {
                deque.add(i);
            }
            return deque;
        }

        int[] degree = new int[n];
        for (int i = 0; i < n; i++) {
            degree[i]=0;
        }
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            degree[edges[i][0]]++;
            degree[edges[i][1]]++;
            Set<Integer> set = map.getOrDefault(edges[i][0], new HashSet<>());
            set.add(edges[i][1]);
            map.put(edges[i][0],set);
            Set<Integer> set1 = map.getOrDefault(edges[i][1], new HashSet<>());
            set1.add(edges[i][0]);
            map.put(edges[i][1],set1);
        }
        int count =0;
        int rest = n;
        for (int i = 0; i < degree.length; i++) {
            if(degree[i]==1){
                deque.offer(i);
                count++;
            }
        }
        if(count==rest){
            return deque;
        }
        while (count!=0||rest!=deque.size()){
            if(count==0){
                count = deque.size();
            }
            Integer in = deque.poll();
            Set<Integer> integers = map.get(in);

                for (int a : integers
                ) {
                    degree[a]--;
                    if (degree[a] == 1) {
                        deque.offer(a);
                    }
                }

            count--;
            rest--;
        }
        return deque;

    }
}
